package Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * \* Created with IntelliJ IDEA.E
 * \* User: Administrator
 * \* Date: 2022/4/24
 * \* Time: 14:16
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
class Node{
    int x;
    int y;
    public Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}

public class Demo1 {

    public static void main(String[] args) {
        int[] arr = {1,3,8,5,6,8};
        int left = 0;
        int right = arr.length-1;
        int mid = left + (right - left)/2;
        System.out.println(arr[mid]);
    }

    public void minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int row = triangle.size();//triangle的大小就是三角矩阵的行
        int[][] path = new int[row][row];//定义path二维数组来存放三角矩阵中每个坐标的状态即最短路径和
        path[0][0] = triangle.get(0).get(0);//状态的初始化
        System.out.println(path[0][0]);

    }

    public static void main12(String[] args) {
        ArrayList<ArrayList<Integer>> num = new ArrayList<ArrayList<Integer>>();
        int index = 1;
        ArrayList<Integer> member1 = new ArrayList<Integer>();
       // System.out.println(member1.add(20));
        member1.add(20);
        member1.add(20);
        member1.add(20);
        member1.add(20);
        num.add(member1);
        int row = 10;
        int [][] path = new int[row][row];
        path[0][0] = num.get(0).get(0);
        System.out.println(path[0][0]);
    }




    /**
     *
     * @param mat 迷宫矩阵 row col
     * @param row 行数
     * @param col 列数
     * @param x  当前位置
     * @param y  当前位置
     * @param book  标记矩阵，标记当前位置是否已经走过
     * @param path  保存当前走过的每一个位置
     * @param minPath 保存最短路径
     */
    public static void getMinPath(int[][] mat, int row, int col, int x, int y,
                                  int[][] book, ArrayList<Node> path,ArrayList<Node> minPath){

        //判断位置是否越界，是否走过，是否有漏洞
        if(x < 0|| x>= row || y<0 || y>=col ||book[x][y]==1 || mat[x][y] ==1){
            return;
        }
        //把当前路径存入路径中
        path.add(new Node(x,y));
        //存入之后，标记该路径
        book[x][y] = 1;
        //判断该路径是否为出口
        if(x == row -1 && y == col -1){
            //如果是，则判断该路径是否为更短的路径
            if(minPath.isEmpty() || path.size() < minPath.size()){
                minPath.clear();
                for (Node n : path){
                    minPath.add(n);
                }
            }
        }
        //继续遍历上下左右四个方向
        getMinPath(mat, row, col, x-1, y, book, path, minPath);
        getMinPath(mat, row, col, x+1, y, book, path, minPath);
        getMinPath(mat, row, col, x, y-1, book, path, minPath);
        getMinPath(mat, row, col, x, y+1, book, path, minPath);

        //把当前位置从路径中删除，寻找新的路径
        path.remove(path.size()-1);
        book[x][y] = 0;
    }
}
